As transistor and other component sizes become smaller and manufacturing techniques continue to improve, more functionality is being placed on single integrated circuits, or chips. The term system on a chip (SoC) generally refers to integrating all the functionality of a computer or other complex electronic system onto a single chip. A SoC may comprise one or more memories, processors, or input/output ports, all integrated into a single chip. One way of allowing various components of a SoC to communicate is to use an on-chip network, sometimes referred to as a network-on-chip. An on-chip network is intended to replace conventional ways of communicating between electronic components in a complex system, such as conventional bus and crossbar interconnections.
On-chip networks may divide network-level packets (e.g. Ethernet frames or Internet Protocol (IP) packets) into smaller data blocks called flits. A node may have multiple flits available for transmission on a virtual channel or other channel resource. One problem in on-chip networks is achieving fairness for flits from different sources competing for virtual channels or other resource. Conventional arbitration techniques, such as round robin, may result in globally unfair bandwidth allocation to different flows (e.g., source-destination pairs), especially when the on-chip network is congested. This is because the bandwidth allocated to a traffic flow may depend at least in part on the number of times the flow participates in arbitrations at intermediate nodes. Consequently, under high network load, flows with longer path lengths receive less bandwidth than flows with shorter path lengths competing for the same resources because packets belonging to longer path flows need to arbitrate at more intermediate nodes. These problems are exacerbated as a number of nodes in an on-chip network increases, and consequently a number of potential intermediate nodes between a source and destination grows.